976F - Minimal k-covering - CodeForces Solution

#include <bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define sws ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
#define teto(a, b) ((a+b-1)/(b))
using namespace std;

// Extra
#define all(x) x.begin(), x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//

const int MAX = 300010;
const ll MOD = (int)1e9 +7;
const int INF = 1e9;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ld EPS = 1e-8;


const int N = 5001;

struct Dinic {
    struct Edge{
        int from, to, idx; ll flow, cap;
    };
    vector<Edge> edge;

    vector<int> g[N];
    int ne = 0;
    int lvl[N], vis[N], pass;
    int qu[N], px[N], qt;

    ll run(int s, int sink, ll minE) {
        if(s == sink) return minE;

        ll ans = 0;

        for(; px[s] < (int)g[s].size(); px[s]++) {
            int e = g[s][ px[s] ];
            auto &v = edge[e], &rev = edge[e^1];
            if(lvl[v.to] != lvl[s]+1 || v.flow >= v.cap)
                continue;           // v.cap - v.flow < lim
            ll tmp = run(v.to, sink,min(minE, v.cap-v.flow));
            v.flow += tmp, rev.flow -= tmp;
            ans += tmp, minE -= tmp;
            if(minE == 0) break;
        }
        return ans;
    }
    bool bfs(int source, int sink) {
        qt = 0;
        qu[qt++] = source;
        lvl[source] = 1;
        vis[source] = ++pass;
        for(int i = 0; i < qt; i++) {
            int u = qu[i];
            px[u] = 0;
            if(u == sink) return true;
            for(auto& ed : g[u]) {
                auto v = edge[ed];
                if(v.flow >= v.cap || vis[v.to] == pass)
                    continue; // v.cap - v.flow < lim
                vis[v.to] = pass;
                lvl[v.to] = lvl[u]+1;
                qu[qt++] = v.to;
            }
        }
        return false;
    }
    ll flow(int source, int sink) {
        reset_flow();
        ll ans = 0;
        //for(lim = (1LL << 62); lim >= 1; lim /= 2)
        while(bfs(source, sink))
            ans += run(source, sink, LLINF);
        return ans;
    }
    void addEdge(int u, int v, int idx, ll c, ll rc) {
        Edge e = {u, v, idx, 0, c};
        edge.pb(e);
        g[u].push_back(ne++);

        e = {v, u, idx, 0, rc};
        edge.pb(e);
        g[v].push_back(ne++);
    }
    void reset_flow() {
        for(int i = 0; i < ne; i++)
            edge[i].flow = 0;
        memset(lvl, 0, sizeof(lvl));
        memset(vis, 0, sizeof(vis));
        memset(qu, 0, sizeof(qu));
        memset(px, 0, sizeof(px));
        qt = 0; pass = 0;
    }
    vector<pair<int, int>> cut() {
        vector<pair<int, int>> cuts;
        for (auto [from, to, idx, flow, cap]: edge) {
            if (flow == cap and vis[from] == pass and vis[to] < pass and cap>0) {
                cuts.pb({from, to});
            }
        }
        return cuts;
    }
};

int grau[N];

int main() {
    sws;
    int n1, n2, m;
    cin >> n1 >> n2 >> m;

    int source = N-1, sink = N-2;
    Dinic dinic;

    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;

        grau[a]++;
        grau[n1+b]++;
        dinic.addEdge(a, b+n1, i+1, 1, 0);
    }

    int menor = m;
    for(int i = 1; i <= n1+n2; i++) {
        menor = min(menor, grau[i]);
    }

    for(int i = 1; i <= n1; i++) {
        dinic.addEdge(source, i, 0, m, 0);
    }
    for(int i = 1; i <= n2; i++) {
        dinic.addEdge(i+n1, sink, 0, m, 0);
    }

    cout << 0 << endl;

    for(int k = 1; k <= menor; k++) {
        dinic.reset_flow();

        for(auto& e : dinic.edge) {
            if(e.from == source or e.from == sink) {
                e.cap = grau[e.to]-k;
            }
            if(e.to == source or e.to == sink) {
                e.cap = grau[e.from]-k;
            }
        }

        vector<int> res;
        dinic.flow(source, sink);
        for(auto& e : dinic.edge) {
            if(e.flow or e.cap == 0) continue;
            if(e.from >= N-2 or e.to >= N-2) continue;

            res.pb(e.idx);
        }

        cout << res.size() << " ";
        for(auto idx : res) {
            cout << idx << " ";
        }
        cout << endl;
    }
    

    return 0;
}